package mincostmaxflow;
import java.util.HashMap;
import java.util.Map;
import java.util.Vector;
import java.util.logging.Level;
import java.util.logging.Logger;

public class BellmanFord {
    
/*
    // this class represents an edge between two nodes
    static class Edge {
        int source; // source node
        int destination; // destination node
        int cost; // weight of the edge
        public Edge() {}; // default constructor
        public Edge(int s, int d, int c) { source = s; destination = d; cost = c; }
    }
*/
//    public static void main(String[] args) {
//        Vector<Edge> edges = new Vector<Edge>(); // a sample vector of edges of some graph
//
//        edges.add(new Edge(1, 2, 2));
//        edges.add(new Edge(2, 1, -2));
//        //edges.add(new Edge(1, 3, 3));
//        edges.add(new Edge(3, 1, -3));
//        edges.add(new Edge(2, 4, 3));
//        //edges.add(new Edge(4, 2, INF));
//        edges.add(new Edge(2, 5, 3));
//        edges.add(new Edge(5, 2, -3));
//        edges.add(new Edge(3, 5, 1));
//        edges.add(new Edge(5, 3, -1));
//        edges.add(new Edge(4, 6, 10));
//        //edges.add(new Edge(6, 4, INF));
//        //edges.add(new Edge(5, 6, 5));
//        edges.add(new Edge(6, 5, -5));
///*
//        edges.add(new Edge(0, 1, 2));
//        edges.add(new Edge(1, 0, -2));
//        //edges.add(new Edge(0, 2, INF));
//        edges.add(new Edge(2, 0, -3));
//        edges.add(new Edge(1, 3, 3));
//        //edges.add(new Edge(3, 1, INF));
//        edges.add(new Edge(1, 4, 3));
//        edges.add(new Edge(4, 1, -3));
//        edges.add(new Edge(2, 4, 1));
//        edges.add(new Edge(4, 2, -1));
//        edges.add(new Edge(3, 5, 10));
//        //edges.add(new Edge(5, 3, INF));
//        //edges.add(new Edge(4, 5, INF));
//        edges.add(new Edge(5, 4, -5));
//*/
//        bellmanFord(edges/*, 6*/, 1, 6);
//    }



//    private static Map<Integer, Integer> getVertices(Vector<Edge> edgs){
    private static Map<Integer, Integer> getVertices(Graph<Edge> edgs){
        Map<Integer, Integer> result = new HashMap<Integer, Integer>();
        for(Edge e : edgs){
            if(!result.containsKey(e.source))
                result.put(e.source, Edge.INF);
            if(!result.containsKey(e.destination))
                result.put(e.destination, Edge.INF);
        }
        return result;
    }
//    static Vector<Edge> bellmanFord(Vector<Edge> edges/*, int nnodes*/, int source, int target) {
    static Route<Edge> bellmanFord(Graph<Edge> edges/*, int nnodes*/, int source, int target) {
        //int[] previous = new int[nnodes];
        //Arrays.fill(previous, INF);
        //previous[source] = -1;

        Route<Edge> result = new Route<Edge>();

        Map<Integer, Integer> prev = getVertices(edges);
        prev.put(source, -1);


        // the 'distance' array contains the distances from the main source to all other nodes
        // at the start - all distances are initiated to infinity
        // the distance from the main source to itself is 0
        Map<Integer, Integer> dist = getVertices(edges);
        dist.put(source, 0);


        // in the next loop we run the relaxation 'nnodes' times to ensure that
        // we have found new distances for ALL nodes
        for (int i = 0; i < dist.size(); ++i)

            // relax every edge in 'edges'

            for(Edge e : edges){
            //for (int j = 0; j < edges.size(); ++j) {
                // analyze the current edge
                //  (SOURCE == edges.get(j).source, DESTINATION == edges.get(j).destination):
                //  if the distance to the SOURCE node is equal to INF then there's
                //  no shorter path from our main source to DESTINATION through SOURCE
                if (dist.get(e.source) == Edge.INF) continue;
                //if (distance[edges.get(j).source] == INF) continue;

                // newDistance represents the distance from our main source to
                //  DESTINATION through SOURCE (i.e. using current edge - 'edges.get(j)')
                int newDistance = dist.get(e.source) + e.cost;
                //int newDistance = distance[edges.get(j).source] + edges.get(j).weight;

                // if the newDistance is less than previous shortest distance
                //  from our main source to DESTINATION
                //  then record that new shortest distance from the main source
                //  to DESTINATION
                if (newDistance < dist.get(e.destination))
                //if (newDistance < distance[edges.get(j).destination])
                {
                    dist.put(e.destination, newDistance);
                    //distance[edges.get(j).destination] = newDistance;
                    prev.put(e.destination, e.source);
                    //previous[edges.get(j).destination] = edges.get(j).source;
                }
            }

        // next loop analyzes the graph for cycles
        for(Edge e : edges)
        //for (int i = 0; i < edges.size(); ++i)

            // 'if (distance[edges.get(i).source] != INF)' means:
            // "if the distance from the main source node to the DESTINATION node
            //  is equal to infinity then there's no path between them"
            //
            // 'if (distance[edges.get(i).destination] >
            //  distance[edges.get(i).source] + edges.get(i).weight)'
            //  says that there's a negative edge weight cycle in the graph
            if (dist.get(e.source) != Edge.INF &&
                    dist.get(e.destination) > dist.get(e.source) + e.cost)
            {
                System.out.println("Negative edge weight cycles detected!");
                return null;
            }

        // this loop outputs the distances from the main source node to all other nodes of the graph
        for (Integer i : dist.keySet())
            if (dist.get(i) == Edge.INF){
                if(i == target){
                    System.out.println("There's no path between " + source + " and " + i);
                    System.out.println("Finished.");
                    return null;
                }
            }
/*
            else{
                //System.out.println("The shortest distance between nodes " + source +
                //        " and " + i + " is " + dist.get(i));//distance[i]);
            }
*/
        
        int q = target;
        Boolean rev = null;
        Edge temp;
        //System.out.print(q);
        while(q != -1 && prev.get(q) != Edge.INF && prev.get(q) != -1)
        //while(q != -1 && previous[q] != INF && previous[q] != -1)
        {
            temp = new Edge(prev.get(q), q, 0);
//            try {
//                rev = MinCostMaxFlow.findEdge(MinCostMaxFlow.getGraph("incrementalGraph"), temp).isReverse;
                rev = edges.findEdge(temp).isReverse;
//            }
//            catch (Exception ex) {
//                Logger.getLogger(BellmanFord.class.getName()).log(Level.SEVERE, null, ex);
//            }
            //System.out.print("<-" + prev.get(q));//previous[q]);
            if(rev != null)
                temp.isReverse = rev;
            result.add(temp);
//            result.toa
            q = prev.get(q);
            //q = previous[q];
        }
        //System.out.println("Shortest path between " + source + " and " + target + " is:");
        //for(Edge e : result)
        //    System.out.println(e);

        return result;
    }
}
